package com.common.model;

/**
 * 并查集
 * 
 * @author think
 */
public class UnionFind {
    private int[] parent;

    private int[] size;

    private int count;

    public UnionFind(int len) {
        parent = new int[len];
        size = new int[len];
        for (int i = 0; i < len; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        count = len;
    }

    public void union(int a, int b) {
        int rootX = find(a);
        int rootY = find(b);
        if (rootX == rootY) {
            return;
        }
        if (size[rootX] > size[rootY]) {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        } else {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
        count--;
    }

    public boolean union1(int a, int b) {
        int rootX = find(a);
        int rootY = find(b);
        if (rootX == rootY) {
            return false;
        }
        if (size[rootX] > size[rootY]) {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        } else {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
        count--;
        return true;
    }

    public int find(int val) {
        while (parent[val] != val) {
            parent[val] = parent[parent[val]];
            val = parent[val];
        }
        return val;
    }

    public int find2(int val) {
        if (parent[val] != val) {
            parent[val] = find(parent[val]);
        }
        return parent[val];
    }

    public boolean isConnect(int a, int b) {
        return find(a) == find(b);
    }

    public int getCount() {
        return count;
    }

    public void setCount(int count) {
        this.count = count;
    }
}